home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2945 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: cymbal.aix.calpoly.edu!not-for-mail
  2. From: dstubbs@cymbal.aix.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 24 Jan 1996 18:17:33 -0800
  6. Organization: California Polytechnic State University, San Luis Obispo
  7. Message-ID: <4e6p7t$1n72@cymbal.aix.calpoly.edu>
  8. References: <4e61iu$p6e@villa.fc.net>
  9. NNTP-Posting-User: dstubbs@cymbal.aix.calpoly.edu
  10.  
  11. In article <4e61iu$p6e@villa.fc.net>,
  12. Avinash Chopde <avinash@paranoia.com> wrote:
  13. >[And no, this is not for a homework exercise.]
  14. >
  15. >I am trying to find out what could be the fastest way to compute
  16. >the position of the highest bit in any given integer -- basically, the
  17. >logarithm to the base 2 of any number.
  18. >
  19. >Simplistically, one could do :
  20. >logbase2(int x)
  21. >{
  22. >    if (IS_SET_BIT_31(x)) return 31;
  23. >    if (IS_SET_BIT_30(x)) return 30;
  24. >    etc.
  25. >}
  26. >
  27. >An improvement would be to check for BITS_31_16 and BITS_15_0 at first, and
  28. >then check for BITS_31_24, and BITS_23_16, etc .. (divide problem in half
  29. >at each stage).
  30. >
  31. >Any thoughts or other ideas?
  32. >
  33. >Thanks!
  34. >
  35. >Avinash Chopde
  36. >e-mail: avinash@acm.org
  37. >home page: http://www.paranoia.com/~avinash/
  38.  
  39. It seems like an interesting exercise to find the left bit using
  40. a binary search since moving an appropriate mask around (for
  41. speed) is a bit "different."  The following is for 32 bit ints,
  42. as you can see it is simple to modify for any width int that is
  43. a power of 2.
  44.  
  45. /*------------------------------------------------------------------*/
  46. int  left_most_bit (int k) {
  47. /*   
  48.  *   returns the position of the left most bit in k assuming that
  49.  *      k != 0 and 32 bit ints. The algorithm used is essentially a
  50.  *      binary search.
  51.  */
  52.    int posn = 0, width = 16, mask = 0xffff0000;
  53.  
  54.    while (width > 1) {
  55.       if (k & mask) {
  56.          width /= 2;
  57.          mask <<= (posn + width);
  58.          mask >>=  posn;
  59.       }
  60.       else {
  61.          mask >>= width;
  62.          posn +=  width;
  63.       }
  64.    } 
  65.    if (k & mask) return posn;
  66.    else return posn+1;
  67. }
  68. /*------------------------------------------------------------------*/
  69.